package B树;

import java.util.Arrays;

public class BTree {
    Node root;
    static class Node{//创建节点
        int [] keys;//关键字
        Node[] children;
        int keyNumber;
        Boolean leaf=true;
        int t;//最小度数
        public Node(int t){
            this.t=t;
            this.children=new Node[2*t];//最大孩纸数
            this.keys=new int[2*t-1];//最多关键字
        }
        @Override
        public String toString(){
            return Arrays.toString(Arrays.copyOfRange(keys,0,keyNumber-1));//打印
        }
       Node get(int key){
            int i=0;
            while (i<keyNumber){
                if(keys[i]==key){
                    return this;
                }
                if(keys[i]>key) {
                    break;
                }
                i++;
            }
            if(leaf){
                return null;//说明该树没有子节点
            }
            return children[i].get(key);//停止的位置便是子节点可能相等的位置
       }
       void insertkey(int key,int index){
            System.arraycopy(keys,index,keys,index+1,keyNumber-index);//把内容往后拷贝
           keys[index]=key;
           keyNumber++;
       }
       void insertChild(Node child,int index){
            System.arraycopy(children,index,children,index+1,keyNumber-index);
            children[index]=child;
       }
    }
    int MIN_KEY_MUMBER;
    int MAX_KEY_MUMBER;
    int t;
    public BTree(){//无参传递
        this(2);
    }
    public BTree(int t){//有参传递
    this.t=t;
    MAX_KEY_MUMBER=2*t-1;
    MIN_KEY_MUMBER=t-1;
    }
    public boolean contain(int key){
        return  root.get(key)!=null;
    }
    public void out(int key){
        doPut(root,key);
    }
    public void doPut(Node node,int key){
        int i=0;
        while (i< node.keyNumber){
            if(node.keys[i]==key){
                return;//更新一下
            }
            if(node.keys[i]>key){
                break;
            }
            i++;
        }
        if(node.leaf){
            node.insertkey(key,i);//如果其为子叶节点，则插入该值
        }
        else {
            doPut(node.children[i],key);//没有在此处找到该值，且该处不是子叶节点因该继续往孩子处查找
        }
    }
    public void spilt(Node left,Node parent,int index){//超过最大关键字时应该拆分
        if(parent==null){//根节点情况
            Node newRoot=new Node(t);
            newRoot.leaf=false;
            newRoot.insertChild(left,0);//一个节点带一个左节点情况
            this.root=newRoot;
            parent=newRoot;
        }
        Node right=new Node(t);
        right.leaf=left.leaf;
        System.arraycopy(left.keys,t,right.keys,0,t-1);//把左侧超出的值全都复制给右侧
        if(!left.leaf){
            System.arraycopy(left.children,t,right.children,0,t);
        }
        right.keyNumber=t-1;
        left.keyNumber=t-1;
        int mid=left.keys[t-1];//把左侧的值调为中侧
        parent.insertChild(right,index+1);
    }





}
